# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

import collections
class Solution:
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return None
        if head.next is None:
            return head
        temp = []
        while head.next is not None:
            temp.append(head.val)
            head = head.next

        i = 0
        while i + 1 < len(temp):
            t = temp[i]
            temp[i] = temp[i + 1]
            temp[i + 1] = t
            i = i + 2

        h = ListNode(temp[0])
        c = ListNode(temp[1])
        h.next = c
        for j in range(2, len(temp)):
            node = ListNode(temp[j])
            c.next = node
            c = c.next
        return h

    def swapPairs2(self, head):

        if not head:
            return None

        if not head.next:
            return head

        cur = head
        nex = head.next

        queueOne = collections.deque([])
        queueTwo = collections.deque([])

        while cur and cur.next:
            queueOne.append(cur)
            queueTwo.append(cur.next)

            cur = cur.next.next

        if cur:
            queueOne.append(cur)

        left = queueTwo.popleft()
        right = queueOne.popleft()
        head = left
        left.next = right

        while queueOne and queueTwo:
            left = queueTwo.popleft()
            right.next = left
            right = queueOne.popleft()
            left.next = right

        if queueOne:
            left = queueOne.popleft()
            right.next = left
        else:
            right.next = None

        return head





